package 左哥算法.ch06二叉树;

import org.junit.Test;

public class Ch05Morris遍历 {

    @Test
    public void test(){
        TreeNode root = TreeNode.newLevelTree(new Integer[]{1, 2, 3, 4, 5, 6, 7, null, null, 8});
        morris(root);
    }

    /**
     * morris遍历，空间复杂度为o(1)，时间复杂度为O（n）
     *  思路：
     *      1.判断当前节点有无左子树，
     *          无左子树则当前节点移动到右子节点
     *          有左子树情况a：如果左子树最右子节点的right为null，则将最右子节点的right指向当前节点，当前节点向左移
     *          有左子树情况b：左子树的最右节点的right为自身，则断掉左子树最右节点的right（指回空），将当前节点移动到右子节点，当前节点右移
     * @param root
     */
    public void morris(TreeNode root){
        while (root!=null){
            if (root.left!=null){
                TreeNode mostRight=root.left;
                while (mostRight.right!=null&&mostRight.right!=root){
                    mostRight=mostRight.right;
                }
                if (mostRight.right==null){
                    System.out.print(root+","); //第一次来到
                    mostRight.right=root;
                    root=root.left;
                    continue;
                }else {
                    mostRight.right=null;
                }
            }
            System.out.print(root+","); //第二次来到
            root=root.right;
        }
    }
}
